package com.hh.TreeQuestions;

import java.util.HashMap;
import java.util.Map;

/**
 * @author hanghao
 * @date 2023/8/3 21:51
 * 路径总和 III
 * middle
 * 给定一个二叉树的根节点root，和一个整数targetSum，求该二叉树里节点值之和等于 targetSum 的路径的数目。
 */
public class No437 {
    public int pathSum(TreeNode root, int targetSum) {
        //key是前缀和, value是大小为key的前缀和出现的次数
        Map<Long, Integer> map = new HashMap<>();
        // 前缀和为0的一条路径
        map.put(0L, 1);
        return recursionPathSum(root, map, targetSum, 0L);
    }

    private int recursionPathSum(TreeNode node, Map<Long, Integer> map, int target, long currSum) {
        // 1.递归终止条件
        if (node == null) {
            return 0;
        }
        // 2.本层要做的事情
        int res = 0;
        // 当前路径上的和
        currSum += node.val;
        //找一个起点 到当前点的距离是target
        res += map.getOrDefault(currSum - target,0);
        // 更新路径上当前节点前缀和的个数
        map.put(currSum,map.getOrDefault(currSum,0) + 1);

        // 3.进入下一层
        res += recursionPathSum(node.left, map, target, currSum);
        res += recursionPathSum(node.right, map, target, currSum);

        // 4.回到本层，恢复状态，去除当前节点的前缀和数量
        map.put(currSum, map.get(currSum) - 1);
        return res;

    }
}
